package java_0220.leetcode;

/**
 * 将BST转为双向链表
 */
public class NumJZ36_ConvertTree {
    /**
     * 传入一个以pRootOfTree为根的BST，就能转为双向链表，并返回链表头节点
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        //对树进行中序遍历：中序遍历出来的链表节点值顺序排列
        //此时的遍历就是一个转换操作，将左子树转换为一个双向链表
        //通过子函数传入Convert(root.left)就转了：这个方法干的事情就是将树转换为双向链表
        //此时leftHead就是左链表的头节点
        TreeNode leftHead=Convert(pRootOfTree.left);
        //继续处理根节点
        //左子树尾节点的next(也就是尾节点的right)==root
        //根节点的前驱要连接左子树的尾节点:root.prev(也就是left)==leftTail
        //此时就要找到链表尾节点，通过遍历找
        TreeNode leftTail=leftHead;
        //注意判空
        while(leftTail!=null&&leftTail.right!=null){
            leftTail=leftTail.right;
        }
        //此时leftTail就处在左侧链表的尾节点
        if(leftTail!=null){
            pRootOfTree.left=leftTail;
            leftTail.right=pRootOfTree;//leftTail。right就是next
        }
        //再递归处理右子树，转换右子树为链表，返回链表头节点
        TreeNode rightHead=Convert(pRootOfTree.right);
        //在和根节点拼接
        if(rightHead!=null){
            //根的右侧就是rightHead,rightHead的left左侧就是根
            pRootOfTree.right=rightHead;
            rightHead.left=pRootOfTree;
        }
        //返回整个大链表的根节点，两种情况
        //1.左树不为空返回左侧头节点
        //2.否则返回根节点
        return leftHead==null?pRootOfTree:leftHead;
    }
}
